/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/insert-interval
   @Language: C++
   @Datetime: 16-02-09 04:49
   */

/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 */

// Method 1, Time O(n), Space O(n)
class Solution {
public:
	/**
	 * Insert newInterval into intervals.
	 * @param intervals: Sorted interval list.
	 * @param newInterval: new interval.
	 * @return: A new interval list.
	 */
	/** Tips : the sorted intervals has no overlap 
	 *         and sort by start in ascending order
	 * sketch:
	 *           1    2     3   4    5      6    7
	 * origin : ---  ---   ---- --  ----  -----  --
	 * new interval: a       ---------
	 * 
	 * step 1: copy intervals whose end less than a's start ---- 1,2 copied
	 * step 2: merge intervals whose start or end in range [a.start, a.end]
	 *         merge a with 3, 4, 5 whose start less than a.end
	 * step 3: append last intervals
	 * */
	vector<Interval> insert(vector<Interval> &A, Interval a) {
		// write your code here
		vector<Interval>::iterator i;
		vector<Interval> v;
		// copy first part intervals whose end less than a.start
		for (i=A.begin(); i!=A.end() && a.start>i->end; v.push_back(*i++));

		// merge intervals whose start or end at range [a.start, a.end]
		// that means intervals whose start <= a.end
		for (; i!=A.end() && a.end>=i->start; ++i)
			a = {min(a.start,i->start), max(a.end,i->end)};
		v.push_back(a);

		// append last intervals to v
		v.insert(v.end(),i,A.end());
		return v;
	}
};

// Method 2, Time O(logn), Space O(1)
class Solution {
	static bool comp(const Interval &a, const Interval &b){
		return a.end<b.start;
	}
public:
	/**
	 * @param intervals: Sorted interval list.
	 * @param newInterval: new interval.
	 * @return: A new interval list.
	 */
	vector<Interval> insert(vector<Interval> &A, Interval &a) {
		// write your code here
		int i=lower_bound(A.begin(),A.end(),a,comp)-A.begin(), j=0;
		for(j=i; j<A.size() && a.end>=A[j].start; ++j)
			a={min(a.start,A[j].start),max(a.end,A[j].end)};
		A.insert(A.begin()+j,a);
		A.erase(A.begin()+i,A.begin()+j);
		return A;
	}
};
